package Arrays;

import java.util.*;

public class _40_CombinationSumII {
    List<List<Integer>> resultList = new ArrayList<List<Integer>>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target){
        Arrays.sort(candidates);
        getSum(candidates,target,0,new ArrayList<Integer>());
        Set<List<Integer>> resultSet = new HashSet<List<Integer>>();
        for(List<Integer> tList:resultList) {
            resultSet.add(tList);
        }
        return new ArrayList<List<Integer>>(resultSet);
    }

    public void getSum(int[] candidates,int target,int pos,List<Integer> curList){
        for(int i=pos;i<candidates.length;i++) {
            if(candidates[i]>target) return;
            int tempSum = target-candidates[i];
            List<Integer> tpList = new ArrayList<Integer>();
            tpList.addAll(curList);
            tpList.add(candidates[i]);
            if (tempSum > 0) {
                getSum(candidates,tempSum,i+1,tpList);
            } else if (tempSum == 0) {
                resultList.add(tpList);
            }else{
                break;
            }
        }
    }
    /*public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> resultList = new ArrayList<List<Integer>>();
        Arrays.sort(candidates);
        int total = target;
        int tempSum = 0;
        int pivot = 0;
        for(int i=candidates.length-1;i>=0;i--) {
            if (candidates[i] <= target) {
                pivot = i;
                break;
            }
        }
        for(int i=pivot;i>=0;i--) {
            List<Integer> tempList = new ArrayList<Integer>();
            tempList.add(candidates[i]);
            total = target-candidates[i];
            int count = i-1;
            if (total == 0) {
                resultList.add(tempList);
            }else {
                for (int j = count; j >= 0; j--) {
                    System.out.println(total+" "+candidates[j]);
                    if (total - candidates[j] >= 0) {
                        if (total - candidates[j] != 0) {
                            total = total - candidates[j];
                            tempList.add(candidates[j]);
                        } else {
                            List<Integer> singleList = new ArrayList<Integer>();
                            singleList.addAll(tempList);
                            singleList.add(candidates[j]);
                            resultList.add(singleList);
                            System.out.println(singleList.toString());
                        }
                    }
                    if (j == 0) {
                        total = target - candidates[i];
                        count--;
                        //if j==count,the circle will sub 1,so j==count+1
                        j = count+1;
                        tempList.clear();
                        tempList.add(candidates[i]);
                        System.out.println("back"+total+" "+candidates[j]);
                        System.out.println(count);
                    }
                }
            }
        }
        Set<List<Integer>> resultSet = new HashSet<List<Integer>>();
        for(List<Integer> tList:resultList) {
            resultSet.add(tList);
        }
        return new ArrayList<List<Integer>>(resultSet);
    }*/
}
